package _021_10_19

func permute(nums []int) [][]int {
	visited := make(map[int]bool)
	var res [][]int
	var dfs func(path []int)
	dfs = func(path []int) {
		if len(path) == len(nums) {
			_res := make([]int, len(nums))
			copy(_res, path)
			res = append(res, _res)
			return
		}
		for i := 0; i < len(nums); i++ {
			if visited[nums[i]] {
				continue
			}
			path = append(path, nums[i])
			visited[nums[i]] = true
			dfs(path)
			path = path[0 : len(path)-1]
			visited[nums[i]] = false
		}
	}
	dfs([]int{})
	return res
}
